实训五     图的操作                                                         

一、实训目的

1.  掌握图的存储思想及其存储实现。

2. 掌握图的深度、广度优先遍历算法思想及其程序实现。

3. 掌握图的常见应用算法的思想及其程序实现。

二、考核办法

必做题部分全做得3分，选做题部分满分2分，至少选一题。

三、实训内容

1.必做内容：（满分3分）

1．键盘输入数据，建立一个无向图的邻接矩阵。如图2

2.结构体部分代码
typedef char vexntype[LEN];
typedef int edgetype;
typedef struct
{
      vexntype vex[VEXN];
      edgetype arc[VEXN][VEXN];
      int vexn,arcn; 
}Mgraph;  
int visit[VEXN];
Mgraph City_Graph()
{
      int i,j,k;
      Mgraph G;
      printf("input vex number:");
       scanf("%d",&G.vexn);
      printf("input edge number:");
       scanf("%d",&G.arcn);
      printf("input %d vex information such as shenyang beijing and so on:\n",G.vexn)
//建立无向图                                                                                                                        图2 无向图
函数（a）
void DFS_G(MGraph *G,int i) //深度遍历算法：
｛…｝

3.要求：（1）完成函数（a）中的递归算法；
（2）编写 main()函数，并调用上述函数，按图2中的无向图形式建立无向图。（3）输出该邻接矩阵。
（4）调用函数（a）将无向图的深度遍历的结果，并输出到屏幕上。
结果如图：

2. 选做内容：（满分2分）

1. 采用邻接表存储实现无向图的广度优先遍历。

2. 编写函数，实现图的拓扑排序。